package com.zc.jianzhi;

import org.junit.Test;

public class Problem41 {

	public int partition(int[] arr,int left,int right) {
		if(left>right||arr==null||arr.length<=0||right>=arr.length) {
			return -1;
		}
		
		int tmp=arr[left];
		
		while(left<right) {
			while(arr[right]>tmp&&left<right) {
				right--;
			}
			
			if(arr[right]<=tmp&&left<right) {
				arr[left++]=arr[right];
			}
			
			while(arr[left]<=tmp&&left<right) {
				left++;
			}
			
			if(arr[right]>tmp&&left<right) {
				arr[right++]=arr[left];
			}
		}
		
		arr[left]=tmp;
		return left;
	}

	
	public int getMedian(int[] arr) throws Exception {
		if(arr==null||arr.length<=0) {
			throw new Exception();
		}
		
		int L=arr.length;
		int mid=L>>1;
		
		int left=0,right=L-1;
		int index = partition(arr,left,right);
		
		while(index!=mid) {
			if(index<mid) {
				left=index+1;
				index=partition(arr,left,right);
			}
			
			if(index>mid) {
				right=index-1;
				index=partition(arr,left,right);
			}
		}
		
		return arr[index];
	}

	public void solution() {

	}
	
	@Test
	public void test() {
		int[] arr= {1,3,2,6,5,4};
		try {
			System.out.println(getMedian(arr));
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}
